package com.hsc.offer;

/**
 * @author
 * @date 2025-06-22
 * @Description 14.输入一个链表，输出该链表中倒数第k个结点。
 */
public class OfferTest9 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode listNode = FindKthToTail(node1, 1);
        System.out.println(listNode.val);

    }

    /**
     * 第一种方法
     * 效率较差
     *
     * @param head 链表
     * @param k    第k个节点
     * @return
     */
    public static ListNode FindKthToTail(ListNode head, int k) {
        //统计节点个数
        int num = 0;
        // 节点定义
        ListNode point = head;
        // 循环获取总工有多少个节点
        while (true) {
            if (point == null) {
                break;
            }
            // 指向链表下一个节点
            point = point.next;
            // 节点数量加1
            num++;
        }
        // 寻找倒数第k个节点
        // 代数第k个节点
        // 如果从头获取就是  总数量减去 k 个
        // 假如有10个节点 倒数第三个节点 就是 顺数的第七个节点 10-3=7
        point = head;
        for (int i = 0; i < num - k; i++) {
            // 从前往后一直寻找 到  num - k 个节点 就是倒数 第 k个节点
            point = point.next;
        }
        return point;
    }

    /**
     * 方法二 只遍历一次
     * <p>
     * 思路：
     * 当前节点 往后移动k个 如果当前 节点+k 个后的节点为null
     * 说明当前节点为倒数第k个
     *
     * @param head 链表
     * @param k    第k个节点
     * @return
     */
    public static ListNode FindKthToTail2(ListNode head, int k) {
        // 当前节点
        ListNode point = head;
        // 循环将当前节点往后移动
        while (true) {
            // 将当前节点的值 赋给 临时变量 temp
            ListNode temp = point;
            // temp 往后遍历 k 个
            for (int i = 0; i < k; i++) {
                //严谨性判断 首次进来 temp就为null  的话  直接返回
                if (temp == null) {
                    return null;
                }
                // 执行k 次next
                temp = temp.next;
            }
            // 上面循环结束 如果说 temp 为null 说明当前元素为倒数第k个节点
            if (temp == null) {
                // 返回的是链表的当前节点
                return point;
            }
            // 否则 链表当前元素继续往下 指向 继续找
            point = point.next;
        }
    }
}

/**
 * 节点类
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;

    }
}

